Introduction

• Many ideas in number theory revolve around how numbers behave modulo $n$.
• Fermat’s Little Theorem is a famous result about powers modulo a prime.
• Euler discovered a powerful generalization that works for any positive integer $n$.
• The key ingredient is a function called the Euler phi-function, written $\varphi(n)$.

This article introduces $\varphi(n)$, explores how to compute it, and shows how it leads naturally to Euler’s Theorem, a broad extension of Fermat’s Little Theorem.

Motivation: Why Count “Coprime” Numbers?

• When working modulo $n$, some numbers behave better than others.
• Numbers that share no common factors with $n$ (other than 1) are called coprime to $n$.
• These numbers:
  • have multiplicative inverses modulo $n$
  • form a natural “multiplicative group” modulo $n$
  • are the ones that matter for generalizing Fermat’s theorem

Key idea:
To understand modular arithmetic deeply, we need to know how many numbers less than $n$ are coprime to it.

Definition of the Euler Phi-Function $\varphi(n)$

• For a positive integer $n$, $$\varphi(n) = \text{the number of integers } 1 \le k \le n \text{ that are coprime to } n.$$
• Examples:
  • $\varphi(1) = 1$ (the number 1 is coprime to itself)
  • $\varphi(2) = 1$ (only 1 is coprime to 2)
  • $\varphi(8) = 4$ (the numbers 1, 3, 5, 7)

First Examples and Computations

Try computing $\varphi(n)$ by listing numbers coprime to $n$:

• $n = 10$
  • Numbers from 1 to 10: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
  • Coprime to 10: 1, 3, 7, 9
  • So $\varphi(10) = 4$
• $n = 12$
  • Coprime numbers: 1, 5, 7, 11
  • So $\varphi(12) = 4$
• $n = 13$ (prime)
  • All numbers 1–12 are coprime to 13
  • So $\varphi(13) = 12$

Patterns begin to emerge, especially for primes and prime powers.

Coprimality and the Structure of the Integers Modulo $n$

• The integers modulo $n$ form a set: $$\{0, 1, 2, \dots, n-1\}.$$
• Among these, the numbers coprime to $n$:
  • are exactly the ones with multiplicative inverses modulo $n$
  • have size $\varphi(n)$
  • form a structure often called the "multiplicative structure modulo $n$"
    • or "multiplicative group modulo $n$"
    • a group is a more rigorous definition from abstract algebra

This structure is what makes Euler’s Theorem possible.

Multiplicative Property of $\varphi(n)$

A key fact:

• If $m$ and $n$ are coprime, then $$\varphi(mn) = \varphi(m)\, \varphi(n).$$

This is called multiplicativity.

Why it matters:

• It allows us to compute $\varphi(n)$ using prime factorization.
• It reduces complicated cases to simpler ones.

Example: Compute $\varphi(66)$

We’ll compute $\varphi(66)$ by breaking 66 into coprime factors, then applying: $$\varphi(mn) = \varphi(m)\, \varphi(n) \quad \text{when } \gcd(m, n)=1.$$

Step 1: Factor 66 into coprime pieces

$$66 = 6 \cdot 11$$ Check coprimality:

• $6 = 2 \cdot 3$
• $11$ is prime
• $\gcd(6, 11)=1$

So the multiplicative property applies.

Step 2: Compute $\varphi(6)$ by listing

Numbers from 1 to 6: $$1, 2, 3, 4, 5, 6$$ Coprime to 6:

• $1$ (coprime)
• $2$ (shares factor 2 → no)
• $3$ (shares factor 3 → no)
• $4$ (shares factor 2 → no)
• $5$ (coprime)
• $6$ (shares factors 2 and 3 → no)

So $$\varphi(6) = 2.$$

Step 3: Compute $\varphi(11)$ using the fact that 11 is prime

For a prime $p$: $$\varphi(p) = p - 1.$$ So $$\varphi(11) = 10.$$

Step 4: Apply the multiplicative property

$$\varphi(66) = \varphi(6)\, \varphi(11) = 2 \cdot 10 = 20.$$

Final Answer

$$\boxed{\varphi(66) = 20}$$

Prime Powers and a Formula for $\varphi(n)$

For a prime $p$ and integer $k \ge 1$: $$\varphi(p^k) = p^k - p^{k-1}$$ Reasoning:

• Among the $p^k$ numbers from $1$ to $p^k$,
  • exactly $p^{k-1}$ are multiples of $p$
  • the rest are coprime to $p^k$

Example: Compute $\varphi(81)$

Step 1: Recognize the prime power

• $81 = 3^4$
• Here $p = 3$ (prime) and $k = 4$

Step 2: Recall the prime powers formula

For a prime $p$ and integer $k \ge 1$, $$\varphi(p^k) = p^k - p^{k-1}$$

Step 3: Apply it to $3^4$

• $p^k = 3^4 = 81$
• $p^{k-1} = 3^3 = 27$

So $$\varphi(81) = 3^4 - 3^3 = 81 - 27 = 54.$$ Final answer: $$\boxed{\varphi(81) = 54}$$

Efficient Computation of $\varphi(n)$

General formula:

If $$n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r},$$ then $$\varphi(n) = n\left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)\cdots\left(1 - \frac{1}{p_r}\right).$$ Steps:

1. Factor $n$ into primes.
2. Apply the formula $$\varphi(n) = n\prod_{p\mid n}\left(1 - \frac{1}{p}\right).$$
3. Simplify.

Example: $n = 60 = 2^2 \cdot 3 \cdot 5$

• $$\varphi(60) = 60\left(1-\frac12\right)\left(1-\frac13\right)\left(1-\frac15\right)$$
• $$= 60 \cdot \frac12 \cdot \frac23 \cdot \frac45 = 16.$$

The special case $n = pq$

• Suppose $n$ is the product of two distinct primes $p$ and $q$.
• Then the set of primes dividing $n$ is just $\{p, q\}$, so the product becomes: $$\varphi(pq) = pq\left(1 - \frac{1}{p}\right)\left(1 - \frac{1}{q}\right).$$

Expand it: $$pq\left(1 - \frac{1}{p}\right)\left(1 - \frac{1}{q}\right) = pq \left(\frac{p-1}{p}\right)\left(\frac{q-1}{q}\right) = (p-1)(q-1).$$ So: $$\varphi(pq) = (p-1)(q-1).$$

Fermat’s Little Theorem Revisited

Fermat’s Little Theorem (FLT):

• If $p$ is prime and $\gcd(a, p)=1$, then $$a^{p-1} \equiv 1 \pmod{p}.$$

Interpretation:

• The exponent $p-1$ is exactly $\varphi(p)$ for a prime $p$.
• This hints that $\varphi(n)$ might play a similar role for composite $n$.

Euler’s Theorem: A Powerful Generalization

Euler’s Theorem:

• If $\gcd(a, n)=1$, then $$a^{\varphi(n)} \equiv 1 \pmod{n}.$$

This reduces to Fermat’s theorem when $n$ is prime.

Why it works:

• The $\varphi(n)$ numbers coprime to $n$ form a multiplicative structure of size $\varphi(n)$.
• Repeated multiplication cycles through this structure.

Comparing Fermat’s and Euler’s Theorems

Euler’s theorem is strictly more general.

Applications in Modular Arithmetic

• Simplifying large powers modulo $n$
• Finding modular inverses
• Understanding the structure of $(\mathbb{Z}/n\mathbb{Z})^\times$
• Reducing computations in algorithms

Simplifying Large Exponents Using Euler’s Theorem

1. The Key Idea

Euler’s theorem states: $$a^{\varphi(n)} \equiv 1 \pmod{n} \quad \text{whenever } \gcd(a,n)=1.$$ This means:

• You can reduce the exponent modulo $\varphi(n)$.
• Instead of computing $a^k$, you compute $a^{\,k \bmod \varphi(n)}$.

This is the main trick.

2. The Basic Procedure

To simplify $a^k \pmod{n}$ using Euler’s theorem:

1. Check coprimality
   Ensure $\gcd(a,n)=1$.
   If not, Euler’s theorem does not apply.
2. Compute $\varphi(n)$
   Use prime factorization if needed.
3. Reduce the exponent
   Replace $k$ with $k \bmod \varphi(n)$.
4. Compute the smaller power
   Now the exponent is manageable.

3. Example 1: Simplifying $7^{100} \bmod 20$

Step 1: Check coprimality

$\gcd(7,20)=1$, so Euler’s theorem applies.

Step 2: Compute $\varphi(20)$

• $20 = 2^2 \cdot 5$
• $\varphi(20) = 20(1-\tfrac12)(1-\tfrac15) = 8$

Step 3: Reduce the exponent

$$100 \bmod 8 = 4$$

Step 4: Compute the reduced power

$$7^{100} \equiv 7^4 \pmod{20}.$$ $$7^4 = 2401 \equiv 1 \pmod{20}.$$ Final result: $$7^{100} \equiv 1 \pmod{20}.$$

4. Example 2: Simplifying $3^{2025} \bmod 14$

Step 1: Check coprimality

$$\gcd(3,14)=1$$

Step 2: Compute $\varphi(14)$

• $14 = 2 \cdot 7$
• $\varphi(14)=14(1-\tfrac12)(1-\tfrac17)=6$

Step 3: Reduce the exponent

$$2025 \bmod 6 = 3$$

Step 4: Compute the reduced power

$$3^{2025} \equiv 3^3 = 27 \equiv 27 - 14 = 13 \pmod{14}.$$ Final result: $$3^{2025} \equiv 13 \pmod{14}.$$

5. Why This Works

• The units modulo $n$ form a multiplicative structure of size $\varphi(n)$.
• Repeated multiplication cycles through this structure.
• After exactly $\varphi(n)$ steps, you return to $1$.
• So any exponent can be reduced modulo $\varphi(n)$.

This is the heart of Euler’s theorem.

Applications to Cryptography (A Gentle Preview)

The RSA cryptosystem uses:

• prime factorization
• Euler’s phi-function
• Euler’s theorem

Key ideas:

• Choose large primes $p$ and $q$
• Compute $n = pq$
• Compute $\varphi(n) = (p-1)(q-1)$
• Use Euler’s theorem to build encryption and decryption exponents

Common Pitfalls and Misconceptions

• Mistake: Thinking $\varphi(n)$ counts all numbers less than $n$.
  • It counts only those coprime to $n$.
• Mistake: Applying Euler’s theorem when $\gcd(a, n)\ne1$.
  • The theorem requires coprimality.
• Mistake: Forgetting to factor $n$ fully before using the formula.
• Mistake: Assuming $\varphi(n)$ is easy to compute for huge $n$.
  • It’s easy only if you know the prime factorization.

Summary and Key Ideas

• $\varphi(n)$ counts numbers coprime to $n$.
• It is multiplicative: $\varphi(mn)=\varphi(m)\varphi(n)$ when $\gcd(m, n)=1$.
• For prime powers: $\varphi(p^k)=p^k-p^{k-1}$.
• General formula uses prime factorization.
• Euler’s theorem: $$a^{\varphi(n)}\equiv1\pmod n \quad\text{if }\gcd(a, n)=1.$$
• Euler’s theorem generalizes Fermat’s Little Theorem.
• These ideas are foundational for modern cryptography.

Calculator

Exercises

1. Compute $\varphi(15)$ by listing numbers coprime to 15.

   Solution

   Compute $\varphi(15)$ by listing numbers coprime to 15.

   • Numbers from 1 to 15: $$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15$$
   • Prime factors of $15$ are $3$ and $5$, so numbers not coprime are multiples of $3$ or $5$.
   • Coprime to $15$: $$1, 2, 4, 7, 8, 11, 13, 14$$

   So $$\varphi(15) = 8.$$

2. Compute $\varphi(36)$ using the prime factorization formula.

   Solution

   Compute $\varphi(36)$ using the prime factorization formula.

   • Factor: $36 = 2^2 \cdot 3^2$
   • Use $$\varphi(n) = n\prod_{p\mid n}\left(1 - \frac{1}{p}\right).$$
   • So $$\varphi(36) = 36\left(1-\frac12\right)\left(1-\frac13\right) = 36 \cdot \frac12 \cdot \frac23 = 12.$$

   So $$\varphi(36) = 12.$$

3. Compute $\varphi(49)$ and explain why the prime-power formula applies.

   Solution

   Compute $\varphi(49)$ and explain why the prime-power formula applies.

   • $49 = 7^2$ is a prime power.
   • For $p$ prime and $k \ge 1$: $$\varphi(p^k) = p^k - p^{k-1}.$$
   • Here $$\varphi(49) = 7^2 - 7^1 = 49 - 7 = 42.$$

   The prime-power formula applies because $49$ is $p^2$ with $p=7$ prime.

4. Use Euler’s theorem to compute $3^{100} \bmod 14$.

   Solution

   Use Euler’s theorem to compute $3^{100} \bmod 14$.

   • First check $\gcd(3, 14)=1$ → yes, so Euler’s theorem applies.
   • Factor $14 = 2 \cdot 7$, so $$\varphi(14) = 14\left(1-\frac12\right)\left(1-\frac17\right) = 14 \cdot \frac12 \cdot \frac67 = 6.$$
   • Euler’s theorem: $$3^6 \equiv 1 \pmod{14}.$$
   • Reduce exponent: $$100 = 6\cdot 16 + 4 \Rightarrow 3^{100} = (3^6)^{16} \cdot 3^4.$$
   • So $$3^{100} \equiv 1^{16} \cdot 3^4 \equiv 3^4 \pmod{14}.$$
   • Compute $3^4 = 81$, and $81 \equiv 81 - 70 = 11 \pmod{14}$.

   So $$3^{100} \equiv 11 \pmod{14}.$$

5. Compute $11^{40} \bmod 21$ using $\varphi(21)$.

   Solution

   Compute $11^{40} \bmod 21$ using $\varphi(21)$.

   • Check $\gcd(11, 21)=1$ → yes.
   • Factor $21 = 3 \cdot 7$, so $$\varphi(21) = 21\left(1-\frac13\right)\left(1-\frac17\right) = 21 \cdot \frac23 \cdot \frac67 = 12.$$
   • Euler’s theorem: $$11^{12} \equiv 1 \pmod{21}.$$
   • Reduce exponent: $$40 = 12\cdot 3 + 4 \Rightarrow 11^{40} = (11^{12})^3 \cdot 11^4.$$
   • So $$11^{40} \equiv 1^3 \cdot 11^4 \equiv 11^4 \pmod{21}.$$
   • Compute stepwise modulo $21$:
     • $11^2 = 121 \equiv 121 - 105 = 16 \pmod{21}$
     • $11^4 = (11^2)^2 \equiv 16^2 = 256 \equiv 256 - 231 = 25 \equiv 4 \pmod{21}$

   So $$11^{40} \equiv 4 \pmod{21}.$$

6. Explain why $\varphi(p)=p-1$ for a prime $p$.

   Solution

   Explain why $\varphi(p)=p-1$ for a prime $p$.

   • For a prime $p$, the numbers from $1$ to $p-1$:
     • are all less than $p$
     • cannot share any common factor with $p$ except $1$, because $p$ has no nontrivial divisors.
   • So every integer $1, 2, \dots, p-1$ is coprime to $p$.
   • There are exactly $p-1$ such numbers.

   Therefore $$\varphi(p) = p - 1.$$

7. Give an example of a number $a$ for which Euler’s theorem cannot be applied modulo $12$, and explain why.

   Solution

   Give an example of a number $a$ for which Euler’s theorem cannot be applied modulo $12$, and explain why.

   • Euler’s theorem requires $\gcd(a, 12)=1$.
   • Take, for example, $a = 6$.
     • $\gcd(6, 12) = 6 \ne 1$.
   • So $6$ is not coprime to $12$, and Euler’s theorem does not apply.

   Any non-coprime example works, e.g. $a=2, 3, 4, 6, 8, 9, 10, 12$.

8. Show that $\varphi(2^k)=2^{k-1}$ and describe the numbers counted by $\varphi(2^k)$.

   Solution

   Show that $\varphi(2^k)=2^{k-1}$ and describe the numbers counted by $\varphi(2^k)$.

   • Use the prime-power formula with $p=2$: $$\varphi(2^k) = 2^k - 2^{k-1} = 2^{k-1}.$$
   • Which numbers are coprime to $2^k$?
     • Exactly the odd numbers between $1$ and $2^k$.
   • There are $2^{k-1}$ odd numbers in $\{1, 2, \dots, 2^k\}$.

   So $\varphi(2^k)$ counts the odd numbers from $1$ to $2^k$.

9. Compute $\varphi(210)$ and list the distinct primes involved.

   Solution

   Compute $\varphi(210)$ and list the distinct primes involved.

   • Factor $210$: $$210 = 2 \cdot 3 \cdot 5 \cdot 7.$$
   • Distinct primes: $2, 3, 5, 7$.
   • Use the formula: $$\varphi(210) = 210\left(1-\frac12\right)\left(1-\frac13\right)\left(1-\frac15\right)\left(1-\frac17\right).$$
   • Compute stepwise:
     • $210 \cdot \frac12 = 105$
     • $105 \cdot \frac23 = 70$
     • $70 \cdot \frac45 = 56$
     • $56 \cdot \frac67 = 48$

   So $$\varphi(210) = 48.$$

10. Use Euler’s theorem to simplify $7^{2025} \bmod 100$.

    Solution

    Use Euler’s theorem to simplify $7^{2025} \bmod 100$.

    • First check $\gcd(7, 100)=1$ → yes.
    • Factor $100 = 2^2 \cdot 5^2$.
    • Compute: $$\varphi(100) = 100\left(1-\frac12\right)\left(1-\frac15\right) = 100 \cdot \frac12 \cdot \frac45 = 40.$$
    • Euler’s theorem: $$7^{40} \equiv 1 \pmod{100}.$$
    • Reduce exponent: $$2025 = 40\cdot 50 + 25 \Rightarrow 7^{2025} = (7^{40})^{50} \cdot 7^{25}.$$
    • So $$7^{2025} \equiv 1^{50} \cdot 7^{25} \equiv 7^{25} \pmod{100}.$$

    Now reduce $7^{25} \bmod 100$:

    • $7^2 = 49$
    • $7^4 \equiv 49^2 = 2401 \equiv 1 \pmod{100}$ (since $2401 = 24\cdot 100 + 1$)
    • So $7^4 \equiv 1 \pmod{100}$.
    • Write $25 = 4\cdot 6 + 1$, so $$7^{25} = (7^4)^6 \cdot 7^1 \equiv 1^6 \cdot 7 \equiv 7 \pmod{100}.$$

    Therefore $$7^{2025} \equiv 7 \pmod{100}.$$